package leet416partitionequalsubsetsum

// 思路：
// 1. 首先判断数组的和是否为偶数，如果不是，则无法分割成两个子集
// 2. 如果是偶数，则目标子集的和为总和的一半
// 3. 使用动态规划来判断是否存在子集和为目标值
// 4. 创建一个布尔数组dp，其中dp[i]表示是否存在子集和为i
// 5. 初始化dp[0]为true，因为空集的和为0
// 6. 遍历数组中的每个元素，对于每个元素，从目标值开始向下遍历，更新dp数组
func CanPartition(nums []int) bool {
	sum := 0
	for _, num := range nums {
		sum += num
	}

	// 如果总和是奇数，则无法分割成两个子集
	if sum%2 != 0 {
		return false
	}

	target := sum / 2
	dp := make([]bool, target+1)
	dp[0] = true // 空集的和为0

	// 解释一下这个动态规划的思路：
	// dp[j] 表示是否存在子集和为 j 的情况。
	// 对于每个数字 num，我们从目标值 target 开始向下遍历，更新 dp 数组。在这个过程中，
	// 如果 dp[j-num] 为 true，说明存在一个子集和为 j-num 的情况，那么加上当前的 num 就可以得到一个子集和为 j 的情况。
	// 因此我们将 dp[j] 更新为 true。
	// 注意这里是从后向前遍历，避免在同一轮中使用同一个数字多次。举个例子说明从前向后遍历会导致错误：
	// 假设 nums = [1, 5, 11, 5]，target = 11，TODO...
	for _, num := range nums {
		for j := target; j >= num; j-- {
			dp[j] = dp[j] || dp[j-num]
		}
	}

	return dp[target]
}

// 换一个思路，上边的思路看不太懂
func CanPartitionSelf(nums []int) bool {
	// sum/2 的概念还是存在，也就是我们的目标和。
	// 定义 dp[i][j] 表示从 [0,i] 这个子集可以得到的最接近j的和的大小。
	// 递推公式: 有两种方式可以推出dp[i][j]的值：
	// 1. 不选择当前元素 nums[i]，则 dp[i][j] = dp[i-1][j]
	// 2. 选择当前元素 nums[i]，则 dp[i][j] = dp[i-1][j-nums[i]] + nums[i](前提是 j >= nums[i])
	// 综上所述，状态转移方程为：
	// dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i])
	n := len(nums)
	if n == 0 {
		return false
	}
	sum := 0
	for _, num := range nums {
		sum += num
	}
	if sum%2 != 0 {
		return false
	}
	target := sum / 2
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, target+1)
	}
	for j := 0; j <= target; j++ {
		if j >= nums[0] {
			dp[0][j] = nums[0]
		}
	}
	for i := 1; i < n; i++ {
		for j := 0; j <= target; j++ {
			if j < nums[i] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
			}
		}
	}
	return dp[n-1][target] == target
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 这个方法是基于动态规划的思想，使用二维数组来存储状态。
// 但是可以进一步优化空间复杂度，将二维数组压缩为一维数组，因为每次只需要前一行的状态。
func CanPartitionOptimized(nums []int) bool {
	sum := 0
	for _, num := range nums {
		sum += num
	}

	if sum%2 != 0 {
		return false
	}

	target := sum / 2
	dp := make([]bool, target+1)
	dp[0] = true // 空集的和为0

	for _, num := range nums {
		for j := target; j >= num; j-- {
			dp[j] = dp[j] || dp[j-num]
		}
	}

	return dp[target]
}
